package com.googlecode.gaal.suffix.algorithm.impl;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

import com.googlecode.gaal.suffix.algorithm.api.ExtendedLcpTableBuilder;
import com.googlecode.gaal.suffix.api.EnhancedSuffixArray;
import com.googlecode.gaal.suffix.api.IntervalTree.Interval;
import com.googlecode.gaal.suffix.api.SuffixTree.Node;

// Get the extended lcp table, which is used for constructing the
// new child table.
public class ExtendedLcpTableBuilderImpl implements ExtendedLcpTableBuilder {

    @Override
    public int[] buildExtendedLcpTable(EnhancedSuffixArray enhancedSuffixArray) {
        int n = enhancedSuffixArray.getSuffixTable().length;
        int[] result = new int[n];
        traverseDepths(enhancedSuffixArray.top(), result, enhancedSuffixArray);
        return result;
    }

    // See method above.
    private static void traverseDepths(Node top, int[] result, EnhancedSuffixArray esa) {
        Iterator<Node> iterator = top.childIterator();
        List<Node> children = new ArrayList<Node>();
        while (iterator.hasNext())
            children.add(iterator.next());
        int n = children.size();

        for (int i = 1; i < n; i++) {
            Interval child = children.get(i);
            int lb = child.left();
            result[lb] = esa.getLcpTable()[lb] * esa.alphabetSize() + depth(i + 1, n);
        }
        for (Node child : children) {
            traverseDepths(child, result, esa);
        }
    }

    private static List<Integer> a006165 = new ArrayList<Integer>();

    static {
        a006165.add(-1);
        a006165.add(1);
        a006165.add(1);
    }

    private static int A006165(int n) {
        n += 2; // offset
        for (int i = a006165.size(); i <= n; i++) {
            if (i % 2 == 1) {
                a006165.add(a006165.get(i / 2) + a006165.get(i / 2 + 1));
            } else {
                a006165.add(2 * a006165.get(i / 2));
            }
        }
        return a006165.get(n);
    }

    // Is this really kind of like an average? How does it compare to
    // other averages?
    private static int avg(int l, int r) {
        return A006165(r - l) + l - 1;
    }

    private static int depthCacheSize = 89; // very arbitrary choice
    private static int[][] depthCache = new int[depthCacheSize][];

    static {
        for (int i = 2; i < depthCacheSize; i++) {
            depthCache[i] = ruler(i);
        }
    }

    private static int[] ruler(int n) {
        int[] result = new int[n + 1];
        ruler(2, n, 0, result);
        return result;
    }

    private static void ruler(int l, int r, int d, int[] result) {
        if (l > r) {
            return;
        }
        int av = avg(l, r);
        ruler(l, av - 1, d + 1, result);
        result[av] = d;
        ruler(av + 1, r, d + 1, result);
    }

    private static int depth(int k, int n) {
        if (n < depthCacheSize) {
            return depthCache[n][k];
        }
        return rdepth(k, 2, n);
    }

    private static int rdepth(int k, int l, int n) {
        int av = avg(l, n);
        if (k == av) {
            return 0;
        }
        if (k < av) {
            return 1 + rdepth(k, l, av - 1);
        }
        return 1 + rdepth(k, av + 1, n);

    }
}
